package sort;

public class HeapSort implements Sort {
    @Override
    public void sort(int[] arr, boolean asc) {
        int len;
        if ((len = arr.length) == 1) {
            return;
        }
        // 1. 构建大/小顶堆
        int[] heap = new int[len];
        heap[0] = arr[0];
        int idx = 1;
        for (; idx < len; ++idx) {
            heap[idx] = arr[idx];
            moveUp(heap, idx, asc);
        }

        // 2. 移动堆顶到末尾
        for (int i = len - 1; i > 0; --i) {
            swap(heap, 0, i);
            moveDown(heap, 0, asc, i);
        }

        // 3. 将调整好的堆赋值给arr
        System.arraycopy(heap, 0, arr, 0, len);
    }
    private void moveUp(int[] arr, int idx, boolean asc) {
        if (idx == 0) {
            return;
        }
        int parentIdx = (idx - 1) / 2;
        if ((asc && arr[idx] > arr[parentIdx]) || (!asc && arr[idx] < arr[parentIdx])) {
            int tmp = arr[idx];
            arr[idx] = arr[parentIdx];
            arr[parentIdx] = tmp;
            moveUp(arr, parentIdx, asc);
        }
    }

    private void moveDown(int[] arr, int idx, boolean asc, int last) {
        int rightIdx = idx * 2 + 2;
        int leftIdx = idx * 2 + 1;
        if (rightIdx < last) {
            // 两个儿子
            if ((asc && arr[idx] < Math.max(arr[leftIdx], arr[rightIdx])) || (!asc && arr[idx] > Math.min(arr[leftIdx], arr[rightIdx]))) {
                int swapIdx = ((asc && arr[leftIdx] > arr[rightIdx]) || (!asc && arr[leftIdx] < arr[rightIdx])) ? leftIdx : rightIdx;
                swap(arr, idx, swapIdx);
                moveDown(arr, swapIdx, asc, last);
            }
        } else if (leftIdx < last) {
            // 只有左儿子
            if ((asc && arr[idx] < arr[leftIdx]) || (!asc && arr[idx] > arr[leftIdx])) {
                int tmp = arr[idx];
                arr[idx] = arr[leftIdx];
                arr[leftIdx] = tmp;
            }
        }
    }

    private void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}
